As higher bandwidth is offered by optical networks, more efficient methods are needed to perform IP lookup and packet classifications in high performance internet routers. In general, a router is connected to several different networks and typically classifies incoming packets into flows utilizing information contained in packet headers and a table of classification rules. This table is called the “router table” (equivalently, rule table). When a computer communicates with another on the Internet, IP data packets are directed from source to destination through a series of routers which read the destination address and re-transmit the packet either to its destination as indicated by the destination address, or to another router which will forward the packet further along until the packet reaches its destination. Each of these intermediate steps between router and destination are referred to as a “next hop.”
The combination of output interface and next hop is referred to as the “route”. Since there is typically more than one route that will ultimately lead a packet to its destination, prior to routing the data packet, the router must learn the set of addresses to which the packet may be forwarded. Typically the appropriate route for a given IP address is encoded in part or all of the IP address itself. The next step for the router is to find a route that corresponds to any of the addresses within this set of addresses. It should be apparent that since there are a range of addresses the router may find more than one route that matches an address for this packet. The router's task is to find the best route, defined by the address that has the most bits in common with the packet's destination address.
Packet classification is generally done using the destination address of a packet. Each router-table rule is a pair of the form (F, NH), where F is a filter and NH is a next hop. A filter is a destination-address prefix that matches all destination addresses for which it is a prefix. The associated rule tables are known as LMPTs and W is used to denote the maximum possible length of a prefix. For example, the filter 10* matches all destination addresses that begin with the bit sequence 10. Through the use of a routing look-up table, the router must determine the output interface port, through which to forward the packet and the next hop for that packet from the node connected to that interface.
Generally, the length of a router-table prefix cannot exceed the length W of a destination address. For Internet Protocol Version 4 (IPv4), the forwarding decision is based on a 32-bit destination address carried in each packet's header and W is considered to be 32 bits. A lookup engine at each port of the router uses a suitable routing data structure to determine the appropriate outgoing link for the packet's destination address. Similarly, for Internet Protocol Version 6 (IPv6), the forwarding decision is based on a 128-bit destination address carried in each packet's header and W is considered to be 128 bits.
Traditionally, a router look-up operation is performed in linear fashion. Each entry in a look-up table is examined for a match. The operation must continue throughout the table even after a match is found to be certain that the best match was found. Since an Internet router-table may contain several rules that match a given destination address d, a tie breaker is used to select a rule from the set of rules that match the destination address. Generally, ties are broken by selecting the next hop associated with the longest prefix that matches the packet's destination address via longest-prefix matching.
Data structures for longest-prefix matching have been intensely researched in recent years. Ternary content-addressible memories (TCAMs) use parallelism to achieve O(1) lookup. Each memory cell of a TCAM may be set to one of three states “0”, “1”, and “?” (don't care). The prefixes of a router table are stored in a TCAM in descending order of prefix length. Assuming that each word of the TCAM has 32 cells, the prefix 10* is stored in a TCAM word as 10??? . . . ?, where ? denotes a don't care and there are 30 ?s in the given sequence. To do a longest-prefix match, the destination address is matched, in parallel, against every TCAM entry and the first (i.e., longest) matching entry reported by the TCAM arbitration logic. Thus, using a TCAM and a sorted-by-length linear list, the longest matching-prefix can be determined in O(1) time. A prefix may be inserted or deleted in O(q) time, where q is the number of different prefix lengths in the table. Although TCAMs provide a simple and efficient solution for static and dynamic router tables, this solution requires specialized hardware, costs more, and uses more power and board space than other current solutions.
Among the vast array of solutions to the problem, few achieve a favorable balance of performance, efficiency, and cost. Dynamic IP router tables have been known in the art and several data structures have been proposed for dynamic LMPTs. (See U.S. Pat. No. 7,031,320 (hereinafter the '320 patent)). In particular, the '320 patent teaches using a skip list for the routing table where lookup, insertions, deletions and updates must be started from the header node (col. 8, lines 22-26). Each node has a single pointer or multiple pointers and the leftmost node is called a header node. In addition, each prefix length has its own hash table to store route entries matching to the corresponding prefix length. Each hash table only stores route entries exactly matching its prefix length (col. 9, lines 17-27). Each node has route entries ranging from 32 to 24 and if route entries exist corresponding to each prefix length ranging from 32 to 24, inclusive, then the corresponding node will have nine (9) pointers to point to nine (9) different hash tables. Although these structures may improve insert/delete complexity, the improvement is at the expense of lookup complexity.
A tree bitmap (TBM) data structure for dynamic LMPTs has been previously proposed by Eatherton et al. in “Tree bitmap: hardware/software IP lookups with incremental updates”. SIGCOMM Comput. Commun. Rev., 34(2):97-122, 2004, to improve lookup complexity. (See also U.S. Pat. App. No. 2005/0157712). Although this data structure results in fast lookups, inserts and deletes make an excessive number of memory accesses. The reasons for the poor performance of TBM on insert and delete operations stem from the fact that, in a TBM, the children of a node are stored in contiguous memory using variable-size memory blocks. This has two detrimental consequences for insert and delete operations. First, a complex memory management system is needed to allocate and deallocate variable size memory blocks. Second, insertion or deletion of a prefix may significantly change the number of children that a node has, causing poor performance. This requires the deallocation of an old memory block and allocation of a new memory block. Consequently, insertion and deletion may require more than 3000 memory accesses each, in the worst case.
Hardware solutions that involve the use of content addressable memory as well as solutions that involve modifications to the Internet Protocol (i.e., the addition of information to each packet) have also been proposed to increase the efficiency of routing packets. Unfortunately, specialized hardware solutions are expensive and are difficult to efficiently individualize to specific needs.
Accordingly, there exists a need for a data structure and method that provides very high lookup and update rates without sacrificing one for the other, that achieves a favorable balance of performance, efficiency, and cost.